#include <iostream>

using namespace std;

// 链表节点
template <typename T>
struct ListNode
{
    T data;         // 数据域
    ListNode *next; // 指针域
    ListNode(T d) : data(d), next(nullptr) {}
    ListNode(T d, ListNode *p) : data(d), next(p) {}
};

// 树节点
template <typename T>
struct TreeNode
{
    T data;                                // 数据域
    ListNode<TreeNode<T> *> *childrenHead; // 指针域（链表头节点）

    TreeNode() : childrenHead(nullptr) {}

    // 添加孩子节点
    void addChild(TreeNode<T> *node)
    {
        ListNode<TreeNode<T> *> *childNode = new ListNode<TreeNode<T> *>(node);
        if (childrenHead == nullptr)
        {
            childrenHead = childNode;
        }
        else
        {
            childNode->next = childrenHead;
            childrenHead = childNode;
        }
    }
};

template <typename T>
class Tree
{

private:
    TreeNode<T> *nodes; // 节点集合
    TreeNode<T> *root;  // 根节点

public:
    Tree();
    Tree(int maxNodes);
    ~Tree();
    // 获取树节点指针
    TreeNode<T> *getTreeNode(int id);
    // 设置根节点
    void setRoot(int rootId);
    // 添加子节点
    void addChildren(int parentId, int sonId);
    // 置数据域
    void assignData(int nodeId, T data);
    // 打印树
    void print(TreeNode<T> *root = nullptr);
};

template <typename T>
Tree<T>::Tree()
{
    nodes = new TreeNode<T>[100001];
}

template <typename T>
Tree<T>::Tree(int maxNodes)
{
    nodes = new TreeNode<T>[maxNodes];
}

template <typename T>
Tree<T>::~Tree()
{
    delete[] nodes;
}

template <typename T>
TreeNode<T> *Tree<T>::getTreeNode(int id)
{
    return &nodes[id];
}

template <typename T>
void Tree<T>::setRoot(int rootId)
{
    root = getTreeNode(rootId);
}

template <typename T>
void Tree<T>::addChildren(int parentId, int sonId)
{
    TreeNode<T> *parentNode = getTreeNode(parentId);
    TreeNode<T> *sonNode = getTreeNode(sonId);
    parentNode->addChild(sonNode);
}

template <typename T>
void Tree<T>::assignData(int nodeId, T data)
{
    getTreeNode(nodeId)->data = data;
}

template <typename T>
void Tree<T>::print(TreeNode<T> *node)
{
    if (node == nullptr)
    {
        node = root;
    }
    cout << node->data << " ";
    ListNode<TreeNode<T> *> *pTemp = node->childrenHead;
    while (pTemp)
    {
        print(pTemp->data); // 直接传递指针节点
        pTemp = pTemp->next;
    }
}

int main()
{
    Tree<char> T(9);
    T.setRoot(0);
    T.assignData(0, 'a');
    T.assignData(1, 'b');
    T.assignData(2, 'c');
    T.assignData(3, 'd');
    T.assignData(4, 'e');
    T.assignData(5, 'f');
    T.assignData(6, 'g');
    T.assignData(7, 'h');
    T.assignData(8, 'i');

    T.addChildren(0, 2);
    T.addChildren(0, 1);
    T.addChildren(1, 3);
    T.addChildren(2, 5);
    T.addChildren(2, 4);
    T.addChildren(3, 8);
    T.addChildren(3, 7);
    T.addChildren(3, 6);

    T.print();

    return 0;
}